using System;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;

namespace Common.Utilities
{
    /// <summary>
    /// 
    /// </summary>
    public class StringUtil
    {
        /// <summary>
        /// 
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        public static string[] Split(string input)
        {
            if (!string.IsNullOrEmpty(input))
            {
                return input.Split(new char[] { ',' });
            }
            else
            {
                return null;
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="input"></param>
        /// <param name="pattern"></param>
        /// <returns></returns>
        public static string[] Split(string input, string pattern)
        {
            if (!string.IsNullOrEmpty(input))
            {
                if (string.IsNullOrEmpty(pattern))
                {
                    return new string[] { input };
                }
                else if(pattern==" ")
                {
                    string[] words = input.Split(new char[] {' '});
                    List<string> wordList = new List<string>();
                    foreach(string word in words)
                    {
                        if(word.Trim().Length>0)
                            wordList.Add(word.Trim());
                    }
                    return wordList.ToArray();
                }
                else
                {
                    int pos = 0;
                    List<string> parts = new List<string>();
                    while (pos >= 0)
                    {
                        int currentPos = input.ToLower().IndexOf(pattern.ToLower(), pos);
                        if (currentPos > pos)
                        {
                            parts.Add(input.Substring(pos, currentPos - pos));
                            pos = currentPos + pattern.Length;
                        }
                        else 
                        {
                            if (pos < input.Length)
                            {
                                parts.Add(input.Substring(pos));
                            }
                            break;
                        }
                    }
                    if (parts.Count > 0)
                    {
                        return parts.ToArray();
                    }
                    else
                    {
                        return null;
                    }
                }
            }
            else
            {
                return null;
            }
        }

		/// <summary>
		/// 
		/// </summary>
		/// <param name="names"></param>
		/// <returns></returns>
		public static List<string> ParseToList(string names)
		{
			List<string> strList = new List<string>();
			string[] nameArray = StringUtil.Split(names);
			if (nameArray != null && nameArray.Length > 0)
				strList.AddRange(nameArray);
			return strList;
		}

		/// <summary>
		/// 
		/// </summary>
		/// <param name="names"></param>
		/// <param name="delimiter"></param>
		/// <returns></returns>
		public static List<string> ParseToList(string names, string delimiter)
		{
			List<string> strList = new List<string>();
			string[] nameArray = StringUtil.Split(names, delimiter);
			if (nameArray != null && nameArray.Length > 0)
				strList.AddRange(nameArray);
			return strList;
		}

		/// <summary>
		/// 
		/// </summary>
		/// <param name="parameters"></param>
		/// <returns></returns>
		public static Dictionary<string, string> ParseToDictionary(string parameters)
		{
			Dictionary<string,string> maps=new Dictionary<string, string>();
			string[] nameValues = StringUtil.Split(parameters);
			if(nameValues !=null && nameValues.Length>0)
			{
				foreach(string nameValue in nameValues)
				{
					string[] pair = StringUtil.Split(nameValue, "=");
					if(pair !=null && pair.Length==2)
					{
						string paramName = pair[0];
						string paramValue = pair[1];
						if(!maps.ContainsKey(paramName))
							maps.Add(paramName, paramValue);
					}
				}
			}
			return maps;
		}

        /// <summary>
        /// 
        /// </summary>
        /// <param name="parts"></param>
        /// <returns></returns>
        public static string ToString(string[] parts)
        {
            string output = string.Empty;
            if (parts != null && parts.Length > 0)
            {
                for (int i = 0; i < parts.Length; i++)
                {
                    output += parts[i];
                    if (i < parts.Length - 1)
                    {
                        output += ",";
                    }
                }
            }
            return output;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="parts"></param>
        /// <param name="pattern"></param>
        /// <returns></returns>
        public static string ToString(string[] parts, string pattern)
        {
            string output = string.Empty;
            if (parts != null && parts.Length > 0)
            {
                for (int i = 0; i < parts.Length; i++)
                {
                    output += parts[i];
                    if (i < parts.Length - 1)
                    {
                        output += pattern;
                    }
                }
            }
            return output;
        }

		/// <summary>
		/// 
		/// </summary>
		/// <param name="list"></param>
		/// <returns></returns>
		public static string ToString(List<string> list)
		{
			string output = string.Empty;
			if (list != null && list.Count > 0)
			{
				for (int i = 0; i < list.Count; i++)
				{
					output += list[i];
					if (i < list.Count - 1)
					{
						output += ",";
					}
				}
			}
			return output;
		}

		/// <summary>
		/// 
		/// </summary>
		/// <param name="list"></param>
		/// <param name="delimiter"></param>
		/// <returns></returns>
		public static string ToString(List<string> list, string delimiter)
		{
			string output = string.Empty;
			if (list != null && list.Count > 0)
			{
				for (int i = 0; i < list.Count; i++)
				{
					output += list[i];
					if (i < list.Count - 1)
					{
						output += delimiter;
					}
				}
			}
			return output;
		}

		/// <summary>
		/// 
		/// </summary>
		/// <param name="maps"></param>
		/// <returns></returns>
		public static string ToString(Dictionary<string,string> maps)
		{
			StringBuilder buffer=new StringBuilder();
			if(maps !=null && maps.Count>0)
			{
				foreach(string key in maps.Keys)
				{
					if (buffer.Length > 0)
						buffer.Append(",");
					string val = maps[key];
					buffer.Append(string.Format("{0}={1}", key, val));
				}
			}
			return buffer.ToString();
		}

		/// <summary>
		/// 
		/// </summary>
		/// <param name="maps"></param>
		/// <param name="delimiter"></param>
		/// <returns></returns>
		public static string ToString(Dictionary<string, string> maps, string delimiter)
		{
			StringBuilder buffer = new StringBuilder();
			if (maps != null && maps.Count > 0)
			{
				foreach (string key in maps.Keys)
				{
					if (buffer.Length > 0)
						buffer.Append(delimiter);
					string val = maps[key];
					buffer.Append(string.Format("{0}={1}", key, val));
				}
			}
			return buffer.ToString();
		}

        /// <summary>
        /// 
        /// </summary>
        /// <param name="collection"></param>
        /// <param name="term"></param>
        /// <returns></returns>
        public static bool Match(string[] collection, string term)
        {
            if (string.IsNullOrEmpty(term))
            {
                return false;
            }
            else if (collection != null && collection.Length > 0)
            {
                foreach (string word in collection)
                {
                    if ((!string.IsNullOrEmpty(word)) && (word.ToLower() == term.ToLower()))
                    {
                        return true;
                    }
                }
                return false;
            }
            else
            {
                // collection is empty
                return false;
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="subject"></param>
        /// <param name="pattern"></param>
        /// <param name="matchType"></param>
        /// <returns></returns>
        public static bool Match(string subject, string pattern, StringMatchType matchType)
        {
            if (pattern.Contains("&&"))
            {
                System.Text.RegularExpressions.Regex splitter = new System.Text.RegularExpressions.Regex("&&");
                string[] patterns = splitter.Split(pattern);
                bool matched = true;
                for (int i = 0; i < patterns.Length; i++)
                {
                    bool submatchSuccess = StringUtil.Match(subject, patterns[i], matchType);
                    if (!submatchSuccess)
                    {
                        matched = false;
                        break;
                    }
                }
                return matched;
            }
            else
            {
                if (pattern.Contains("||"))
                {
                    List<string> patterns2=new List<string>();
                    int lastPos = 0;
                    int pos = pattern.IndexOf("||");
                    while(pos>=0)
                    {
                        string subPattern2 = pattern.Substring(lastPos, pos - lastPos);
                        if(!string.IsNullOrEmpty(subPattern2.Trim()))
                        {
                            patterns2.Add(subPattern2.Trim());
                        }
                        lastPos = pos + "||".Length;
                        pos = pattern.IndexOf("||", lastPos);
                    }
                    if (lastPos < pattern.Length)
                    {
                        string subPattern3 = pattern.Substring(lastPos);
                        if(subPattern3.StartsWith("||"))
                        {
                            subPattern3 = subPattern3.Substring(2);
                        }
                        if(subPattern3.EndsWith("||"))
                        {
                            subPattern3 = subPattern3.Substring(0, subPattern3.Length - 2);
                        }
                        patterns2.Add(subPattern3);
                    }
                    
                    bool matched = false;
                    for(int i=0;i<patterns2.Count;i++)
                    {
                        bool matchSuccess = StringUtil.Match(subject, patterns2[i], matchType);
                        if(matchSuccess)
                            return true;
                    }
                    return matched;
                }
                else
                {
                    if (matchType == StringMatchType.RegexMatch)
                    {
                        System.Text.RegularExpressions.Regex regex = new System.Text.RegularExpressions.Regex(pattern, System.Text.RegularExpressions.RegexOptions.IgnoreCase);
                        System.Text.RegularExpressions.Match match = regex.Match(subject);
                        return match.Success;
                    }
                    else
                    {
                        if (subject.ToLower().IndexOf(pattern.ToLower()) >= 0)
                            return true;
                        else
                            return false;
                    }
                }
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="pattern"></param>
        /// <returns></returns>
        public static string BuildRegexMatchPattern(string pattern)
        {
            StringBuilder buffer0 = new StringBuilder();

            string[] optionalPatterns = pattern.Split(new char[] {'\n'});
            for(int i=0;i<optionalPatterns.Length;i++)
            {
                string opPattern = optionalPatterns[i];
                opPattern = opPattern.Trim();
                if(opPattern.Length>0)
                {
                    if (buffer0.Length > 0)
                        buffer0.Append("|");

                    string[] tokens = opPattern.Split(new char[] { ' ', '\t' });
                    char[] escapes = new char[] { '(', '[', '{', ')', ']', '}', '!', '$', '.', '+' };

                    StringBuilder buffer1=new StringBuilder();
                    foreach (string token in tokens)
                    {
                        if (token.Trim().Length > 0)
                        {
                            if (buffer1.Length > 0)
                                buffer1.Append("\\s+");
                            string token1 = token;
                            token1 = token1.Replace("\\", "\\\\");
                            foreach (char escape in escapes)
                            {
                                token1 = token1.Replace(escape.ToString(), "\\" + escape.ToString());
                            }
                            buffer1.Append(token1);
                        }
                    }
                    buffer0.Append("(" + buffer1.ToString() + ")");
                }
            }
            
            return buffer0.ToString();
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="subjects"></param>
        /// <param name="objects"></param>
        /// <returns></returns>
        public static bool Intersects(string[] subjects, string[] objects)
        {
            List<string> commons = new List<string>();
            if (subjects == null || subjects.Length == 0)
                return false;
            if (objects == null || objects.Length == 0)
                return false;
            for (int i = 0; i < subjects.Length; i++)
            {
                if (subjects[i].Trim().Length > 0)
                {
                    commons.Add(subjects[i].Trim().ToLower());
                }
            }
            for (int i = 0; i < objects.Length; i++)
            {
                if (commons.Contains(objects[i].ToLower().Trim()))
                    return true;
            }
            return false;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="words1"></param>
        /// <param name="words2"></param>
        /// <returns></returns>
        public static string[] Intersection(string[] words1, string[] words2)
        {
            List<string> commons = new List<string>();
            List<string> commons2 = new List<string>();
            if (words1 == null || words1.Length == 0)
                return null;
            if (words2 == null || words2.Length == 0)
                return null;
            for (int i = 0; i < words1.Length; i++)
            {
                if (words1[i].Trim().Length > 0)
                {
                    commons.Add(words1[i].Trim().ToLower());
                }
            }
            for (int i = 0; i < words2.Length; i++)
            {
                if (commons.Contains(words2[i].ToLower().Trim()))
                    commons2.Add(words2[i].ToLower().Trim());
            }
            if (commons2.Count > 0)
                return commons2.ToArray();
            else
                return null;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="words1"></param>
        /// <param name="words2"></param>
        /// <returns></returns>
        public static List<string> Intersection(List<string> words1, List<string> words2)
        {
            List<string> commons = new List<string>();
            List<string> commons2 = new List<string>();
            if (words1 == null || words1.Count == 0)
                return null;
            if (words2 == null || words2.Count == 0)
                return null;
            for (int i = 0; i < words1.Count; i++)
            {
                if (words1[i].Trim().Length > 0)
                {
                    commons.Add(words1[i].Trim().ToLower());
                }
            }
            for (int i = 0; i < words2.Count; i++)
            {
                if (commons.Contains(words2[i].ToLower().Trim()))
                    commons2.Add(words2[i].ToLower().Trim());
            }
            return commons2;
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="words1"></param>
        /// <param name="words2"></param>
        /// <param name="maxEditDistanceInWord"></param>
        /// <param name="totalMaxEditDistance"></param>
        /// <returns></returns>
        public static List<string> Intersection(List<string> words1, List<string> words2, int maxEditDistanceInWord, int totalMaxEditDistance)
        {
            if(words1==null || words2==null || words1.Count==0 || words2.Count==0)
                return null;
            List<string> commonWords=new List<string>();
            foreach(string word1 in words1)
            {
                if(!string.IsNullOrEmpty(word1))
                    commonWords.Add(word1.ToLower());
            }
            words1 = commonWords;
            commonWords=new List<string>();
            int totalEdits = 0;
            foreach (string word2 in words2)
            {
                if (!string.IsNullOrEmpty(word2))
                {
                    if (words1.Contains(word2.ToLower()))
                        commonWords.Add(word2);
                    else
                    {
                        int editDistance = -1;
                        foreach (string word1 in words1)
                        {
                            int editDist = StringUtil.EditDistance(word1, word2, false);
                            if (editDistance < 0 || editDist < editDistance)
                                editDistance = editDist;
                        }
                        if (editDistance >= 0 && editDistance <= maxEditDistanceInWord &&
                            totalEdits + editDistance < totalMaxEditDistance)
                        {
                            totalEdits += editDistance;
                            commonWords.Add(word2.ToLower());
                        }
                    }
                }
            }
            return commonWords;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="set1"></param>
        /// <param name="set2"></param>
        /// <returns></returns>
        public static List<string> GetIntersection(string[] set1, string[] set2)
        {
            List<string> intersection = new List<string>();
            List<string> setA = new List<string>();
            if(set1 !=null && set1.Length>0)
            {
                for(int i=0;i<set1.Length;i++)
                {
                    if (set1[i].Trim().Length > 0)
                    {
                        setA.Add(set1[i].Trim().ToLower());
                    }
                }
            }
            if (set2 != null && set2.Length > 0)
            {
                for (int i = 0; i < set2.Length; i++)
                {
                    if (set2[i].Trim().Length > 0)
                    {
                        if(setA.Contains(set2[i].Trim().ToLower()))
                        {
                            intersection.Add(set2[i].Trim());
                        }
                    }
                }
            }
            return intersection;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="subjects"></param>
        /// <param name="objects"></param>
        /// <returns></returns>
        public static string[] Unions(string[] subjects, string[] objects)
        {
            List<string> colls = new List<string>();
            if (subjects == null || subjects.Length == 0)
                return objects;
            if (objects == null || objects.Length == 0)
                return subjects;
            for (int i = 0; i < subjects.Length; i++)
            {
                if (subjects[i].Trim().Length > 0)
                {
                    colls.Add(subjects[i].Trim().ToLower());
                }
            }
            for (int i = 0; i < objects.Length; i++)
            {
                if (!colls.Contains(objects[i].ToLower().Trim()) && objects[i].Trim().Length > 0)
                {
                    colls.Add(objects[i].ToLower().Trim());
                }
            }
            return colls.ToArray();
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="subjects"></param>
        /// <param name="obj"></param>
        /// <returns></returns>
        public static bool Contains(string[] subjects, string obj)
        {
            if (subjects == null || subjects.Length == 0)
                return false;
            if (obj != null && obj.Length == 0)
                return true;
            for (int i = 0; i < subjects.Length; i++)
            {
                if (obj == null && subjects[i] == null)
                    return true;
                if (obj != null && subjects[i] != null && obj.ToLower().Trim() == subjects[i].ToLower().Trim())
                    return true;
            }
            return false;
        }

        #region fuzzy search
        /// <summary>
        /// 
        /// </summary>
        /// <param name="s1"></param>
        /// <param name="s2"></param>
        /// <returns></returns>
        public static int LongestCommonSubsequence(string s1, string s2)
        {
            //if either string is empty, the length must be 0
            if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
                return 0;

            s1 = s1.ToUpper();
            s2 = s2.ToUpper();
            int[,] num = new int[s1.Length, s2.Length];  //2D array
            //Actual algorithm
            for (int i = 0; i < s1.Length; i++)
            {
                for (int j = 0; j < s2.Length; j++)
                {
                    char letter1;
                    char letter2;
                    letter1 = s1[i];
                    letter2 = s2[j];

                    if (letter1 == letter2)
                    {
                        if ((i == 0) || (j == 0))
                            num[i, j] = 1;
                        else
                            num[i, j] = 1 + num[i - 1, j - 1];
                    }
                    else
                    {
                        if ((i == 0) && (j == 0))
                            num[i, j] = 0;
                        else if ((i == 0) && !(j == 0))   //First ith element
                            num[i, j] = Math.Max(0, num[i, j - 1]);
                        else if (!(i == 0) && (j == 0))   //First jth element
                            num[i, j] = Math.Max(num[i - 1, j], 0);
                        else if (!(i == 0) && !(j == 0))
                            num[i, j] = Math.Max(num[i - 1, j], num[i, j - 1]);
                    }
                }//end j
            }//end i

            return num[s1.Length - 1, s2.Length - 1];
        } 

        /// <summary>
        /// BUG: the method to return matched string from content is still BUGGY!!
        /// http://en.wikipedia.org/wiki/Longest_common_subsequence
        /// function  LCSLength(X[1..m], Y[1..n])
        ///     C = array(0..m, 0..n)
        ///     for i := 0..m
        ///         C[i,0] = 0
        ///     for j := 1..n
        ///         C[0,j] = 0
        ///     for i := 1..m
        ///         for j := 1..n
        ///             if X[i] = Y[j]
        ///                 C[i,j] := C[i-1,j-1] + 1
        ///             else:
        ///                 C[i,j] := max(C[i,j-1], C[i-1,j])
        ///     return C[m,n]
        /// </summary>
        /// <param name="content"></param>
        /// <param name="pattern"></param>
        /// <param name="matchedStringInContent"></param>
        /// <returns></returns>
        public static int LongestCommonSubsequence(string content, string pattern, ref string matchedStringInContent)
        {
            //if either string is empty, the length must be 0
            if (String.IsNullOrEmpty(content) || String.IsNullOrEmpty(pattern))
                return 0;

            int fromContent = 1;
            int toContent = content.Length-1;
            content = content.ToUpper();
            pattern = pattern.ToUpper();
            int[,] num = new int[content.Length, pattern.Length];  
            for (int i = 0; i < content.Length; i++)
            {
                for (int j = 0; j < pattern.Length; j++)
                {
                    if (content[i] == pattern[j])
                    {
                        if ((i == 0) || (j == 0))
                        {
                            num[i, j] = 1;
                        }
                        else
                            num[i, j] = 1 + num[i - 1, j - 1];
                    }
                    else
                    {
                        int numberUpper = 0;
                        int numberLeft = 0;
                        if (j > 0)
                            numberLeft = num[i, j - 1];
                        if (i > 0)
                            numberUpper = num[i - 1, j];

                        num[i, j] = Math.Max(numberLeft, numberUpper);
                    }
                }
            }

            int subseqLen = num[content.Length - 1, pattern.Length - 1];
            if(subseqLen==0)
            {
                matchedStringInContent = string.Empty;
            }
            else
            {
                int i = content.Length - 1;
                int j = pattern.Length - 1;
                while (i >= 0 && j >= 0)
                {
                    if (num[i, j] == 1)
                    {
                        fromContent = i;
                        break;
                    }
                    else
                    {
                        if (num[i, j] == subseqLen)
                        {
                            toContent = i;
                        }
                        if (i > 0 && j > 0)
                        {
                            if (num[i, j] == num[i - 1, j - 1])
                            {
                                i--;
                                j--;
                            }
                            else if (num[i, j] == num[i - 1, j])
                                i--;
                            else if (num[i, j] == num[i, j - 1])
                                j--;
                            else
                            {
                                i--;
                                j--;
                            }
                        }
                        //else if (i > 0)
                        //{
                        //    i--;
                        //}
                        //else if (j > 0)
                        //{
                        //    j--;
                        //}
                        //if (num[i, j] >= num[i - 1, j] && num[i, j] >= num[i, j - 1])
                        //{
                        //    i--;
                        //    j--;
                        //}
                        //else if (num[i, j] > num[i - 1, j])
                        //{

                        //}
                    }
                }

                matchedStringInContent = content.Substring(fromContent, toContent - fromContent + 1);
                //matchedStringInContent = ReadCommonSubSequence(num, content, pattern, content.Length - 1,
                //                                               pattern.Length - 1);
            }

            return subseqLen;
        }

        private static string ReadCommonSubSequence(int[,] num, string content, string pattern, int i, int j)
        {
            if (i == 0 || j == 0)
            {
                if (content[i] == pattern[j])
                    return content[i].ToString();
                else
                    return string.Empty;
            }
            if (content[i] == pattern[j])
                return ReadCommonSubSequence(num, content, pattern, i - 1, j - 1) + content[i];
            else
            {
                if(num[i-1,j-1]==num[i-1,j] && num[i-1,j-1]==num[i,j-1])
                {
                    return ReadCommonSubSequence(num, content, pattern, i-1, j - 1) + content[i];
                }
                else
                {
                    if (num[i, j - 1] > num[i - 1, j])
                        return ReadCommonSubSequence(num, content, pattern, i, j - 1);
                    else
                        return ReadCommonSubSequence(num, content, pattern, i - 1, j);
                }
                
            }
        }

        /// <summary> 
        /// http://en.wikipedia.org/wiki/Longest_common_substring_problem 
        /// 
        /// function LCSubstr(S[1..m], T[1..n]) 
        /// L := array(0..m, 0..n) 
        /// z := 0 
        /// ret := {} 
        /// for i := 1..m 
        /// for j := 1..n 
        /// if S[i] = T[j] 
        /// L[i,j] := L[i-1,j-1] + 1 
        /// if L[i,j] > z 
        /// z := L[i,j] 
        /// ret := {} 
        /// if L[i,j] = z 
        /// ret := ret {S[i-z+1..i]} 
        /// return ret 
        /// </summary> 
        /// <param name="subj"></param> 
        /// <param name="pattern"></param> 
        /// <returns></returns> 
        public static int LongestCommonSubString(string subj, string pattern)
        {
            if (string.IsNullOrEmpty(subj) || string.IsNullOrEmpty(pattern))
                return 0;

            subj = subj.ToLower();
            pattern = pattern.ToLower();
            int[,] L = new int[subj.Length, pattern.Length];
            int z = 0;
            for (int i = 0; i < subj.Length; i++)
            {
                for (int j = 0; j < pattern.Length; j++)
                {
                    if (subj[i] == pattern[j])
                    {
                        if (i > 0 && j > 0)
                        {
                            L[i, j] = L[i - 1, j - 1] + 1;
                        }
                        else
                        {
                            L[i, j] = 1;
                        }
                        if (L[i, j] > z)
                        {
                            z = L[i, j];
                        }
                    }
                }
            }
            return z;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="s1"></param>
        /// <param name="s2"></param>
        /// <param name="caseSensitive"></param>
        /// <returns></returns>
        public static int EditDistance(string s1, string s2, bool caseSensitive)
        {
            if (s1==null || s2==null)
                return -1;
            if(caseSensitive)
            {
                s1 = s1.ToUpper();
                s2 = s2.ToUpper();
            }
            // Convert the parameters into IList instances
            // in order to obtain indexing capabilities
            char[] charVals1 = s1.ToCharArray();
            char[] charVals2 = s2.ToCharArray();

            // Get the length of both.  If either is 0, return
            // the length of the other, since that number of insertions
            // would be required.
            int n = charVals1.Length;
            int m = charVals2.Length;
            if (n == 0) return m;
            if (m == 0) return n;

            // Rather than maintain an entire matrix (which would require O(n*m) space),
            // just store the current row and the next row, each of which has a length m+1,
            // so just O(m) space. Initialize the current row.
            int curRow = 0, nextRow = 1;
            int[][] rows = new int[][] { new int[m + 1], new int[m + 1] };
            for (int j = 0; j <= m; ++j) rows[curRow][j] = j;

            // For each virtual row (since we only have physical storage for two)
            for (int i = 1; i <= n; ++i)
            {
                // Fill in the values in the row
                rows[nextRow][0] = i;
                for (int j = 1; j <= m; ++j)
                {
                    int dist1 = rows[curRow][j] + 1;
                    int dist2 = rows[nextRow][j - 1] + 1;
                    int dist3 = rows[curRow][j - 1] +
                        (charVals1[i - 1].Equals(charVals2[j - 1]) ? 0 : 1);

                    rows[nextRow][j] = Math.Min(dist1, Math.Min(dist2, dist3));
                }

                // Swap the current and next rows
                if (curRow == 0)
                {
                    curRow = 1;
                    nextRow = 0;
                }
                else
                {
                    curRow = 0;
                    nextRow = 1;
                }
            }

            // Return the computed edit distance
            return rows[curRow][m];

        }

        /// <summary>
        /// http://siderite.blogspot.com/2007/04/super-fast-and-accurate-string-distance.html
        /// </summary>
        /// <param name="s1"></param>
        /// <param name="s2"></param>
        /// <param name="maxOffset"></param>
        /// <returns></returns>
        public static float SiftDistance(string s1, string s2, int maxOffset)
        {
            if (String.IsNullOrEmpty(s1))
                return String.IsNullOrEmpty(s2) ? 0 : s2.Length;
            if (String.IsNullOrEmpty(s2))
                return s1.Length;
            int c = 0;
            int offset1 = 0;

            int offset2 = 0;
            int lcs = 0;
            while ((c + offset1 < s1.Length) && (c + offset2 < s2.Length))
            {
                if (s1[c + offset1] == s2[c + offset2])
                    lcs++;
                else
                {
                    offset1 = 0;
                    offset2 = 0;
                    for (int i = 0; i < maxOffset; i++)
                    {
                        if ((c + i < s1.Length) && (s1[c + i] == s2[c]))
                        {
                            offset1 = i;
                            break;
                        }
                        if ((c + i < s2.Length) && (s1[c] == s2[c + i]))
                        {
                            offset2 = i;
                            break;
                        }
                    }
                }
                c++;
            }
            return (s1.Length + s2.Length)/2 - lcs;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="content"></param>
        /// <param name="pattern"></param>
        /// <param name="useRegex"></param>
        /// <returns></returns>
        public static double FuzzyStringMatch(string content, string pattern, bool useRegex)
        {
            StringMatchType matchType = StringMatchType.ExactMatch;
            if (useRegex)
                matchType = StringMatchType.RegexMatch;
            if (StringUtil.Match(content, pattern, matchType))
                return 1.0;
            else
            {
                double subseqScore = 0.0;
                string matchedString = string.Empty;
                int subseqLen = StringUtil.LongestCommonSubsequence(content, pattern, ref matchedString);
                if (!string.IsNullOrEmpty(matchedString) && subseqLen > 0)
                    subseqScore = ((double) subseqLen)/Math.Max(matchedString.Length, pattern.Length);

                int subStrLenSum = 0;
                string[] patternWords = StringUtil.Split(pattern, " ");
                foreach (string patternWord in patternWords)
                {
                    int commonSubStringLen = StringUtil.LongestCommonSubString(content, patternWord);
                    subStrLenSum += commonSubStringLen;
                }
                double subStringScore = (double)subStrLenSum / pattern.Length;
                return Math.Max(subseqScore, subStringScore);
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="content"></param>
        /// <param name="patterns">ordered list of patterns</param>
        /// <param name="matchedPattern">best matched pattern</param>
        /// <param name="useRegex"></param>
        /// <returns></returns>
        public static double FuzzyStringMatch(string content, string[] patterns, ref string matchedPattern, bool useRegex)
        {
            double bestScore = double.NegativeInfinity;
            matchedPattern = string.Empty;
            foreach(string pattern in patterns)
            {
                string patternToMatch = pattern;
                if(useRegex)
                {
                    patternToMatch = StringUtil.BuildRegexMatchPattern(patternToMatch);
                }
                double score = StringUtil.FuzzyStringMatch(content, patternToMatch, useRegex);
                if(score > bestScore)
                {
                    bestScore = score;
                    matchedPattern = pattern;
                }
            }
            return bestScore;
        }
        #endregion

        #region clean
        /// <summary>
        /// 
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        public static string RemoveNonAlphaNumericCharacters(string input)
        {
            if (!string.IsNullOrEmpty(input))
            {
                Regex nonAlphaNumRegex = new Regex("^[^a-z0-9]$", RegexOptions.IgnoreCase);
                return nonAlphaNumRegex.Replace(input, "");
            }
            else
            {
                return string.Empty;
            }
        }

        public static bool IsAlphaNumeric(string input)
        {
            if (string.IsNullOrEmpty(input))
            {
                return false;
            }
            input = input.ToLower();
            Regex alphaNumRegex = new Regex("^[a-z0-9]+$", RegexOptions.IgnoreCase);
            return alphaNumRegex.IsMatch(input);
        }

        public static bool IsNumber(string input)
        {
            if (string.IsNullOrEmpty(input))
            {
                return false;
            }
            Regex alphaNumRegex = new Regex("^[-+]?[0-9]*\\.?[0-9]+$", RegexOptions.IgnoreCase);
            return alphaNumRegex.IsMatch(input);
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        public static string RemoveNonAsciiCharacters(string input)
        {
            if(!string.IsNullOrEmpty(input))
            {
                // these characters are invalid in xml 
                for(int i=0;i<=7;i++)
                {
                    input = input.Replace(Convert.ToChar(i).ToString(), "");
                }
                for(int i=11; i<=12;i++)
                {
                    input = input.Replace(Convert.ToChar(i).ToString(), "");
                }
                for(int i=14;i<=31;i++)
                {
                    input = input.Replace(Convert.ToChar(i).ToString(), "");
                }
                Regex specialCharacterRegex = new Regex("[^\x20-\x7E]");
                return specialCharacterRegex.Replace(input, "");
            }
            else
                return string.Empty;
        }
        #endregion

    }

}
